package com.wxc.rbtree;

/**
 * @program: LoveDataStructures1
 * @description: [用一句话描述此类]
 * @author: wxc
 * @create: 2021-07-28 21:45
 **/
public class RedBlackTree<E> extends BalanceBinarySearchTree<E>{
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    public RedBlackTree(IComparator<E> comparator) {
        this.comparator = comparator;
    }

    public RedBlackTree() {
    }

    @Override
    protected Node<E> createNode(E element, Node<E> left, Node<E> right, Node<E> parent) {
        return new RBNode<>(element, left, right, parent);
    }

    // 结点染色
    private Node<E> dyeing(Node<E> node,boolean color) {
        if (node == null) return null;
        ((RBNode<E>)node).color = color;
        return node;
    }

    private Node<E> dyeingRed(Node<E> node) {
        return dyeing(node,RED);
    }

    private Node<E> dyeingBlack(Node<E> node) {
        return dyeing(node,BLACK);
    }

    // 判断是什么颜色
    private boolean colorOf(Node<E> node) {
        return node == null ? BLACK : ((RBNode<E>)node).color;
    }

    private boolean isBlack(Node<E> node) {
        return colorOf(node) == BLACK;
    }

    private boolean isRed(Node<E> node) {
        return colorOf(node) == RED;
    }

    @Override
    protected void afterAdd(Node<E> node) {
        RBNode<E> parentNode = (RBNode<E>) node.parent;
        // 没有父结点
        if(parentNode == null) {
            dyeingBlack(node);
            return;
        }
        // 父结点是黑色
        if(isBlack(parentNode)) return;
        // 父结点是红色
        else {
            // 拿到uncle结点
            Node<E> uncleNode = parentNode.getSibling();
            // 拿到祖父节点
            Node<E> grandNode = parentNode.parent;
            // 父结点是红色说明一定有祖父节点
//            if(grandNode == null) {
//                dyeingBlack(parentNode);
//                return;
//            }
            // uncle结点是红色
            if(isRed(uncleNode)) {
                dyeingBlack(parentNode);
                dyeingBlack(uncleNode);
                dyeingRed(grandNode);
                // 把祖父节点当做是新添加的结点
                afterAdd(grandNode);
                return;
            }
            // LL RR LR RL
            else {
                if(parentNode.isLeftChildNode()) {
                    // LL
                    if(node.isLeftChildNode()){
                        dyeingBlack(parentNode);
                        dyeingRed(grandNode);

                        rotateRight(grandNode);
                    }
                    // LR
                    else {
                        dyeingBlack(node);
                        dyeingRed(grandNode);

                        rotateLeft(parentNode);
                        rotateRight(grandNode);
                    }
                }
                else {
                    // RL
                    if(node.isLeftChildNode()){
                        dyeingBlack(node);
                        dyeingRed(grandNode);

                        rotateRight(parentNode);
                        rotateLeft(grandNode);
                    }
                    // RR
                    else {
                        dyeingBlack(parentNode);
                        dyeingRed(grandNode);

                        rotateLeft(grandNode);
                    }
                }

            }
        }
    }

    @Override
    // 1: Red<-Black->Red
    // 2: Black->Red
    // 3: Red-<Black
    // 4: Black
    protected void afterRemove(Node<E> node, Node<E> replaceNode) {
        // 1/2/3 Red
        if(isRed(node)) return;
        // 被删除的结点是Black
        else {
            // 用于替代的子节点是红色 null也是黑色
            // 由于node是黑色 所以要染成黑色
            if(isRed(replaceNode)) {
                dyeingBlack(replaceNode);
                return;
            }
            // 删除的是黑色叶子结点
            else {
                // 如果删除的是根节点
                Node<E> parentNode = node.parent;
                if(parentNode == null) return;
                // 不是根节点
                else {
                    /**
                     * 			 80
                     * 			/  \
                     * 		   /    \
                     * 		  76    88
                     * 		   \
                     * 		   78(红)
                     */

                    /**
                     * 		   	 80
                     * 			/  \
                     * 		   /    \
                     * 		  76    88
                     * 		 /
                     * 		72(红)
                     */

                    /**
                     * 		     80
                     * 			/  \
                     * 		   /    \
                     * 		  76    88
                     * 		 /  \
                     * 	(红)72  78(红)
                     */
                    // 拿到兄弟结点
                    // 这样写是有问题的
                    // 因为 ndoe是叶子结点 在isLeftChildNode()这个函数中parent.left == this;永远为false
                    // 因为在删除叶子结点remove()方法逻辑中有node.parent.left = null;
                    // Node<E> siblingNode = node.getSibling();
                    // 找到被删除的是左边还是右边
                    // node.isLeftChildNode() 是为了解决父结点下溢的情况，parent先没断掉
                    boolean left = parentNode.left == null || node.isLeftChildNode();
                    Node<E> siblingNode = left ? parentNode.right : parentNode.left;
                    // 被删除的结点在左边
                    if(left) {
                        // 兄弟结点是红色
                        if(isRed(siblingNode)) {
                            // 兄弟染成黑色
                            dyeingBlack(siblingNode);
                            // 父结点染成红色
                            dyeingRed(parentNode);
                            // 对父结点进行右旋
                            rotateLeft(parentNode);
                            // 旋转完父结点变成红色 现在兄弟结点变成黑色
                            // 和删除一个度为2的子节点的代码形式很像
                            // 删除 nextNode 这步太妙了
                            // node = nextNode;
                            // 更换兄弟
                            siblingNode = parentNode.right;
                        }
                        // 兄弟结点是黑色
                        // 看我的黑兄弟能不能借 -> 能借的话兄弟要有红子节点
                        if(isBlack(siblingNode.left) && isBlack(siblingNode.right)) {
                            // 父结点要向下合并
                            boolean parentNodeBlack = isBlack(parentNode);
                            dyeingBlack(parentNode);
                            dyeingRed(siblingNode);
                            if(parentNodeBlack) {
                                afterRemove(parentNode,null);
                            }
                        }
                        // 至少有一红 向兄弟结点借
                        else {
                            if(isBlack(siblingNode.right)) {
                                rotateRight(siblingNode);
                                // 改变sibling
                                siblingNode = parentNode.right;
                            }
                            // 先染色 再旋转
                            dyeing(siblingNode,colorOf(parentNode));
                            dyeingBlack(siblingNode.right);
                            dyeingBlack(parentNode);

                            // 统一右旋
                            rotateLeft(parentNode);

                        }
                    }
                    // 被删除结点在右边
                    else {
                        // 兄弟结点是红色
                        if(isRed(siblingNode)) {
                            // 兄弟染成黑色
                            dyeingBlack(siblingNode);
                            // 父结点染成红色
                            dyeingRed(parentNode);
                            // 对父结点进行右旋
                            rotateRight(parentNode);
                            // 旋转完父结点变成红色 现在兄弟结点变成黑色
                            // 和删除一个度为2的子节点的代码形式很像
                                // 删除 nextNode 这步太妙了
                                // node = nextNode;
                            // 更换兄弟
                            siblingNode = parentNode.left;
                        }
                        // 兄弟结点是黑色
                        // 看我的黑兄弟能不能借 -> 能借的话兄弟要有红子节点
                        if(isBlack(siblingNode.left) && isBlack(siblingNode.right)) {
                            // 父结点要向下合并
                            boolean parentNodeBlack = isBlack(parentNode);
                            dyeingBlack(parentNode);
                            dyeingRed(siblingNode);
                            if(parentNodeBlack) {
                                afterRemove(parentNode,null);
                            }
                        }
                        // 至少有一红 向兄弟结点借
                        else {
                            if(isBlack(siblingNode.left)) {
                                rotateLeft(siblingNode);
                                // 改变sibling
                                siblingNode = parentNode.left;
                            }
                            // 先染色 再旋转
                            dyeing(siblingNode,colorOf(parentNode));
                            dyeingBlack(siblingNode.left);
                            dyeingBlack(parentNode);

                            // 统一右旋
                            rotateRight(parentNode);

                        }
                    }
                }
            }
        }
    }

    protected static class RBNode<E> extends Node<E> {
        // 默认RED
        boolean color = RED;

        public RBNode(E element, Node<E> left, Node<E> right, Node<E> parent) {
            super(element, left, right, parent);
        }

        @Override
        public String toString() {
            if(parent == null) return element + "-P(null)";
            return element + "-P(" + parent.element + ')';
        }
    }

    @Override
    public String string(Node<E> node) {
        if(isRed(node)) return "R_" + node.toString();
        return node.toString();
    }
}
